#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode *Tree;
struct TreeNode {
    int v;
    Tree Left, Right;
    int height;
};
Tree NewNode(int input);
int MakeTree(int N);
Tree Insert(Tree T, int input);
Tree SingleLeftRotation(Tree A);
Tree SingleRightRotation(Tree A);
Tree DoubleLeftRightRotation(Tree A);
Tree DoubleRightLeftRotation(Tree A);
int Max(int a, int b);
int GetHeight(Tree T);
int MakeTree(int N)
{
    int input,i;
    Tree T = NULL;
    for (i = 0; i < N; i++)
    {
        scanf("%d", &input);
        T = Insert(T,input);
    }
    return T->v;

}

Tree NewNode(int input)
{
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = input;
    T->Left = T->Right = NULL;
    T->height = 1;
    return T;
}

Tree Insert(Tree T, int input)
{
    if(!T)//空树
        T = NewNode(input);
    else if(input==T->v)
    {
        //do nothing
    }
    else if(input>T->v)
    {
        T->Right = Insert(T->Right, input);
        if(GetHeight(T->Left) - GetHeight(T->Right) == -2)
        {
            if (input>T->Right->v)//因为前面insert了右子树 所以右子树一定有值
                T = SingleRightRotation(T);
            else
                T = DoubleRightLeftRotation(T);
        }
    }
    else if(input<T->v)
    {
        T->Left = Insert(T->Left, input);
        if(GetHeight(T->Left) - GetHeight(T->Right)==2)
        {
            if (input<T->Left->v)
                T = SingleLeftRotation(T);
            else
                T = DoubleLeftRightRotation(T);
        }
    }
    T->height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;

    return T;
}
int Max(int a,int b)
{
    return a > b ? a : b;
}
int GetHeight(Tree T)
{
    if(T != NULL)
        return T->height;
    else
        return 0;
}
Tree SingleLeftRotation(Tree A)
{
    Tree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->height = Max(GetHeight(B->Left), A) + 1;
    return B;
}
Tree SingleRightRotation(Tree A)
{
    Tree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->height = Max(GetHeight(B->Right), A) + 1;
    return B;
}

Tree DoubleLeftRightRotation(Tree A)
{
    A->Left = SingleRightRotation(A->Left);
    return SingleLeftRotation(A);
}
Tree DoubleRightLeftRotation(Tree A)
{
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}
int main()
{
    int N, L;
    scanf("%d", &N);
    L = MakeTree(N);
    printf("%d\n", L);
    return 0;
}